package first.niuke.simple;

import java.util.Arrays;

/**
 * @ClassName NC126
 * @description:
 * @author: 荣燊
 * @create: 2021-06-13 20:36
 **/
public class NC126 {
    /**
     * 换钱的最少货币数
     * dp[i]表示凑成面额i的需要的最少货币数。
     * dp[i] = min{dp[i-arr[0]], ... ,dp[i-arr[n]]};
     */
    public static void main(String[] args) {
        int[] ints = new int[1];
        System.out.println(ints[0]);
        System.out.println(Integer.MAX_VALUE);


    }

    public int minMoney (int[] arr, int aim) {
        // write code here
        if (aim == 0) {
            return 0;
        }
        if (arr == null || arr.length == 0) {
            return -1;
        }
        // dp[aim]
        int[] dp = new int[aim+1];

        Arrays.fill(dp, Integer.MAX_VALUE-1); //为什么这么使用？
        dp[0] = 0;

        for (int i=1; i<=aim; i++) {
            for (int j=0; j<arr.length; j++) {
                if (i - arr[j] >= 0) {
                    dp[i] = Math.min(dp[i], dp[i-arr[j]]+1);
                }
            }
        }
        return dp[aim] == Integer.MAX_VALUE-1 ? -1 : dp[aim];
    }
}
